package com.tgy.algorithm.base;

import java.util.Arrays;

class MyHeap01 {
    private int[] nums;
    private int size;
    private int limit;
    public MyHeap01(int limit) {
        this.limit = limit;
        this.nums = new int[limit];
        this.size = 0;
    }

    public void insert(int value) {
        if (size >= limit) {
            throw new RuntimeException("超出最大容器");
        }
        int index = size;
        nums[size++] = value;
        //
        //                   5
        //              4           3
        //          1       3
        // (size -  1) >> 1
        while (index > 0) {
            int parent  =  (index - 1) >> 1;
            if (nums[parent] < value) {
                swap(nums, parent, index);
            }
            index  = parent;
        }
    }

    public int heapify() {
        if (size == 0) {
            throw new RuntimeException("栈为空");
        }
        int result = nums[0];

        this.swap(nums, 0, size - 1);
        size--;

        int index = 0;
        int changeIndex = index;
        while (true) {

            int leftIndex = (index << 1)  +  1;
            if (leftIndex >= size) {
                break;
            }

            changeIndex = index;
            if(nums[index] < nums[leftIndex]) {
                changeIndex = leftIndex;
            }

            if(leftIndex + 1 < size) {
                if (nums[changeIndex] < nums[leftIndex + 1]) {
                    changeIndex = leftIndex + 1;
                }
            }

            if(changeIndex != index) {
                swap(nums, changeIndex, index);
            }

            index++;
        }

        return result;
    }

    public  void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    @Override
    public String toString() {
        return Arrays.toString(nums);
    }
}

public class _堆排序01 {
    public static void main(String[] args) {
        MyHeap01 myHeap01 = new MyHeap01(6);
        myHeap01.insert(4);
        myHeap01.insert(3);
        System.out.println(myHeap01);
        myHeap01.insert(2);
        System.out.println(myHeap01);
        /**
         *             5
         *          4     2
         *       3
         *
         */
        myHeap01.insert(5);
        System.out.println(myHeap01);
        myHeap01.heapify();
        System.out.println(myHeap01);
    }
}
